#include<sstream>
#include<vector>
#include<iostream>
#include<gtest/gtest.h>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* stringToListNode(string input);


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        if(head->next == nullptr) return head;

        ListNode* p = head;
        // ListNode* q = new ListNode();
        ListNode* q;
        while(p){
            q = p;
            p = p->next;
        }
        // 原首节点特殊处理，next 设置null
        // ListNode* temp = new ListNode(head->val);
        // head = head->next;
        // temp->next = nullptr;
        // q->next = temp;

        ListNode* temp = head;
        head = head->next;
        temp->next = nullptr;
        q->next = temp;

        ListNode* m = head;
        ListNode* temp2;
        // 未到最后一个节点，插入q之后
        while( q && m && m != q){
            temp2 = m;
            m = m->next;
            temp2->next = q->next;
            q->next = temp2;
        }
        return q;
    }

    // 取巧 利用std::reverse 反转string，再利用平台提供的 stringToListNode 构造一个
    ListNode* reverseList2(ListNode* head) {
        if(!head) return nullptr;
        // 仅有1个节点，直接返回
        if(head->next == nullptr) return head;

        string str;
        ListNode* p = head;
        while(p){
            str.append(std::to_string(p->val));
            p = p->next;
        }
        std::reverse(str.begin(), str.end());
        string str2;
        str2.append("[");
        for(std::string::iterator s = str.begin(); s != str.end(); s++){
            
            str2.insert(str2.end(), *s);
            str2.append(",");
        }
        str2.append("]");

        return stringToListNode(str2);
    }

    // 双指针
    ListNode* reverseList3(ListNode* head){
        if(!head || !head->next ) return head;

        ListNode* cur = nullptr;
        ListNode* pre = head;
        // 首节点特殊处理
        
        while(pre){
            ListNode* temp = pre->next;
            pre->next = cur;
            cur = pre;
            pre = temp;
        }
        return cur;
    }

    // 递归解法,结合画图来理解
    // 递归函数的定义：反转以 head为头节点的链表，并返回反转完成后的链表头节点
    ListNode* reverseList4(ListNode* head){
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* last = reverseList4(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

ListNode* stringToListNode(string input) {
    // Generate list from the input
    vector<int> list = stringToIntegerVector(input);

    // Now convert that list into linked list
    ListNode* dummyRoot = new ListNode(0);
    ListNode* ptr = dummyRoot;
    for(int item : list) {
        ptr->next = new ListNode(item);
        ptr = ptr->next;
    }
    ptr = dummyRoot->next;
    delete dummyRoot;
    return ptr;
}

string listNodeToString(ListNode* node) {
    if (node == nullptr) {
        return "[]";
    }

    string result;
    while (node) {
        result += to_string(node->val) + ", ";
        node = node->next;
    }
    return "[" + result.substr(0, result.length() - 2) + "]";
}



void test_01(){
    string line = "[1,2,3,4,5]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList(head);

    string out = listNodeToString(ret);
    assert(out.size() == 15 );
    cout << out << endl;
}

void test_02(){
    string line = "[1,2]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList(head);

    string out = listNodeToString(ret);
    assert(out.size() == 6 );
    cout << out << endl;
}

void test_03(){
    string line = "[1]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList(head);

    string out = listNodeToString(ret);
    assert(out.size() == 3 );
    cout << out << endl;
}

void test_04(){
    string line = "[1,2,3,4,5]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList2(head);

    string out = listNodeToString(ret);
    assert(out.size() == 15 );
    cout << out << endl;
}
 
void test_05(){
    string line = "[1,2]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList2(head);

    string out = listNodeToString(ret);
    assert(out.size() == 6 );
    cout << out << endl;
} 

void test_06(){
    string line = "[1,2,3,4,5]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList3(head);

    string out = listNodeToString(ret);
    assert(out.size() == 15 );
    cout << out << endl;
}

void test_07(){
    string line = "[1,2,3,4,5]";
    ListNode* head = stringToListNode(line);
        
    ListNode* ret = Solution().reverseList4(head);

    string out = listNodeToString(ret);
    assert(out.size() == 15 );
    cout << out << endl;
}


int main() {
    // test_01();
    // test_02();
    // test_03();
    // test_04();
    // test_05();
    // test_06();
    test_07();

    return 0;
}